/*
 * 2.2
 * Implement an algorithm to find the nth to last element of a singly linked list.
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct _node_t {
    int v;
    struct _node_t *next;
} node_t;

node_t *find_nth_last(node_t *head, int n)
{
    node_t *fast, *slow;
    int i = 0;
    fast = head;
    while (++i <= n && fast->next) {
        fast = fast->next;
    }
    if (i < n) {
        return NULL;
    }
    slow = head;
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

node_t *new_node(int v)
{
    node_t *node = (node_t *)malloc(sizeof(node_t));
    node->v = v;
    return node;
}

int main()
{
    node_t *head = new_node(0);
    node_t *curr, *prev;
    int i = 1;
    prev = head;
    while (i < 7) {
        curr = new_node(i);
        prev->next = curr;
        prev = curr;
        i++;
    }
    /* test */
    node_t *find = find_nth_last(head, 2);
    printf("find last 2 = %d\n", find ? find->v : -1);
    find = find_nth_last(head, 10);
    printf("find last 10 = %d\n", find ? find->v : -1);
    /* free */
    prev = head;
    while (prev) {
        curr = prev->next;
        free(prev);
        prev = curr;
    }
}
